package org.yzhang3.data.bean;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;

import org.yzhang3.data.common.Constants;

public class HuffmanTree {

	private HuffmanNode root;
	/** encode alphabet, after experiment, find alphabet's key's rang is [0, 255].*/
	private Map<Integer, String> alphabet__;
	
	public HuffmanTree(Map<Integer, Integer> counterMap) {

		PriorityQueue<HuffmanNode> nodeQueue = new PriorityQueue<HuffmanNode>();
		
		for (Entry<Integer, Integer> entry : counterMap.entrySet()) {
			nodeQueue.add(new HuffmanNode(entry.getValue().intValue(), entry.getKey().intValue()));
		}
		
		HuffmanNode node1, node2, addedNode;
		while (nodeQueue.size() > 1) {
			node1 = nodeQueue.poll();
			node2 = nodeQueue.poll();
			addedNode = new HuffmanNode(node1.getWeight() + node2.getWeight());
			addedNode.setLeftNode(node1);
			addedNode.setRightNode(node2);
			
			nodeQueue.add(addedNode);
		}
		
		root = nodeQueue.poll();
		
		alphabet__ = new HashMap<Integer, String>(counterMap.size());
		produceAlphabet(root, "");
	}
	
	public  Map<Integer, String> alphabet() {
		return alphabet__;
	}
	
	public void produceAlphabet(HuffmanNode node, String code) {
		if (node.isLeaf()) {
			alphabet__.put(node.getData(), code);
		} else {
			if (null != node.getLeftNode()) {// 0
				produceAlphabet((HuffmanNode) node.getLeftNode(), code + Constants.BINARY_ZERO);
			}
			if (null != node.getRightNode()) {// 1
				produceAlphabet((HuffmanNode) node.getRightNode(), code + Constants.BINARY_ONE);
			}
		}
	}
	
}
